package anthology.leet_code_hot;

import java.util.Arrays;
import java.util.Stack;

//https://leetcode.cn/problems/daily-temperatures/description/
public class _739每日温度 {
    //单调栈
    class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            int length = temperatures.length;
            int[] ans = new int[length];
            Stack<Integer> stack = new Stack<>();
            for(int i = 0; i <length; i++){
                int T = temperatures[i];
                while (!stack.isEmpty() && T > temperatures[stack.peek()]){
                    int tmp = stack.pop();
                    ans[tmp] = i - tmp;
                }
                stack.push(i);
            }
            return ans;
        }
    }
    //暴力 从后往前
    class Solution2 {
        public int[] dailyTemperatures(int[] temperatures) {
            int length = temperatures.length;
            int[] ans = new int[length];
            int[] next = new int[110];
            Arrays.fill(next, Integer.MAX_VALUE);
            for(int i=length-1; i>=0; i--){
                int warmerIndex = Integer.MAX_VALUE;
                for(int t = temperatures[i]+1; t<=100; t++){
                    if(next[t] < warmerIndex) {
                        warmerIndex = next[t];
                    }
                }
                if(warmerIndex < Integer.MAX_VALUE)
                    ans[i] = warmerIndex - i;
                next[temperatures[i]] = i;
            }
            return ans;
        }
    }
    //暴力 从前向后 超时
    class Solution3 {
        public int[] dailyTemperatures(int[] temperatures) {
            int length = temperatures.length;
            int[] result = new int[length];
            for(int i=0; i<length; i++){
                int a = temperatures[i];
                if(a<=100){
                    for (int j=i+1; j<length; j++){
                        if(temperatures[j] > a){
                            result[i] = j-i;
                            break;
                        }
                    }
                }
            }
            return result;
        }
    }

}
